package com.bee.剑指offer;

/**
 * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * 平衡二叉树（Balanced Binary Tree），具有以下性质：
 * 1，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
 * 2，并且左右两个子树都是一棵平衡二叉树。
 */
public class 平衡二叉树 {

    private boolean flag = true;

    /**
     * 使用去数的深度方法就可以求出来，递归，分别求出，左子树，右子树，深度，记录深度，之后，
     * 之后左右子数的高度差不能 left - right <= 1
     */
    public boolean IsBalanced_Solution(TreeNode root) {
        int i = depthTree(root);
        return flag;
    }

    private static volatile boolean co = true;

    public static int depth(TreeNode head) {
        if(head == null) {
            return 0;
        }
        int left = depth(head.left);
        int right = depth(head.right);
        if(Math.abs(left - right) > 1) {
            co = false;
        }
        return left > right ? left + 1 : right + 1;
    }

    /**
     * 使用的求树的深度可以永安里判断树是不是一个平衡二叉树
     */
    public int depthTree(TreeNode head) {
        if(head == null) {
            return 0;
        }
        int left = depthTree(head.left);
        int right = depthTree(head.right);
        if(Math.abs(left - right) > 1) {
            flag = false;
        }
        return left > right ? left + 1 : right + 1;
    }

    private static int sumCount = 0;

    /**
     * 求总节点数
     */
    public void sumNode(TreeNode head) {
        if(head == null) {
            return;
        }
        sumCount++;
        sumNode(head.left);
        sumNode(head.right);
    }

    private static int leftCount = 0;

    /**
     * 求叶子节点的数量
     */
    public void leafNodeCount(TreeNode head) {
        if(head == null) {
            return;
        }
        if(head.left == null && head.right == null) {
            leftCount++;
        }
        leafNodeCount(head.left);
        leafNodeCount(head.right);
    }


    public static void main(String[] args) {

    }
}
